#include "stdafx.h"
#include "graph.h"

using std::vector;
using std::list;


CGraph::CGraph( int _cV, int _cE, Type _type )
	: cV( _cV ), cE( _cE ), type( _type ) {

	struct SYSTEMTIME * start, * end;
	
	if( _type == Matrix ) {

		gMatrix = new int * [ _cV ];

		for ( int i=0; i<_cV; ++i ) {

			gMatrix[i] = new int[_cV];

			for ( int j=0; j<_cV; ++j ) {

				gMatrix[i][j] = 0;
			}
		}
		
	} else {

		gLists.resize( _cV );
	}
}

CGraph::~CGraph() {

	if( type == Matrix ) {

		for ( int i=0; i<cV; ++i ) {

			delete [] gMatrix[i];
		}

		delete [] gMatrix;

	} else {
	
		gLists.clear();
	}
}

int ** CGraph::RandomMatrix( GType _gtype )
{
	int tmp = cE;
	int ** matrix;

	matrix = new int * [ cV ];

	for ( int i=0; i<cV; ++i ) {

		matrix[i] = new int[cV];

		for ( int j=0; j<cV; ++j ) {

			matrix[i][j] = 0;
		}
	}


	srand ( (unsigned)time(NULL) );

	if(_gtype==UnDirect)
	{
		for(int i=1; i<cV&&tmp; i++)
		{
			matrix[0][i] = matrix[i][0] = rand() % 128 + 1;
			tmp--;

		}
		while(tmp)
		{
			int i = rand() % cV; 
			int j = rand() % cV;
			if((i!=j)&&(!matrix[i][j])&&tmp)
			{
				matrix[i][j] = matrix[j][i] = rand() % 128 + 1;
				tmp--;
			}

		}
	}
	else
	{
		for(int i=1; i<cV&&tmp; i++)
		{
			matrix[0][i] = rand() % 257 - 128; //-128...128
			tmp--;

		}
		while(tmp)
		{
			int i = rand() % cV; 
			int j = rand() % cV;
			if((i!=j)&&(!matrix[i][j])&&tmp)
			{
				matrix[i][j] = rand() % 257 - 128;
				tmp--;
			}

		}
	}

	return matrix;
}
int CGraph::GetCountV() {


	return cV;
}

int CGraph::GetCountE() {


	return cE;
}

int CGraph::GetWeight( int vSrc, int vDst ) {

	vSrc--;
	vDst--;

	if ( vSrc < cV && vDst < cV ) {

		if( type == Matrix ) {

			return gMatrix[ vSrc ][ vDst ];

		} else {

			for (int i=0; i<gLists[ vSrc ].size(); ++i) {

				if (gLists[vSrc][i].vB == vDst + 1) {
					
					return gLists[vSrc][i].weight;
				}
			}
		}
	}


	return INT_MAX;
}

vector< int > CGraph::GetConsequents( int v ) {

	vector< int > vertices;
	v--;


	if ( v < cV ) {

		if( type == Matrix ) {

			for ( int i=0; i<cV; ++i ) {

				if ( gMatrix[ v ][ i ] != 0 ) {

					vertices.push_back( i + 1 );
				}
			}

		} else {

			for (int i=0; i<gLists[v].size(); ++i) {

				vertices.push_back( gLists[v][i].vB );
			}
		}
	}


	return vertices;
}

bool CGraph::AddDirectEdge( int vSrc, int vDst, int weight ) {

	struct edge edge;


	vSrc--;
	vDst--;

	if ( vSrc < cV && vDst < cV ) {

		if( type == Matrix ) {

			gMatrix[ vSrc ][ vDst ] = abs( weight );
			
			return true;
	
		} else {

			edge.vA = vSrc + 1;
			edge.vB = vDst + 1;
			edge.weight = abs( weight );
			gLists[ vSrc ].push_back( edge );

			return true;
		}
	}


	return false;
}

bool CGraph::AddUndirectEdge( int vA, int vB, int weight ) {

	struct edge edgeA;
	struct edge edgeB;


	vA--;
	vB--;

	if ( vA < cV && vB < cV && weight >= 0 ) {

		if( type == Matrix ) {

			gMatrix[ vA ][ vB ] = weight;
			gMatrix[ vB ][ vA ] = weight;
			
			return true;
	
		} else {

			edgeA.vA = vA + 1;
			edgeA.vB = vB + 1;
			edgeA.weight = weight;
			gLists[ vA ].push_back( edgeA );
			
			edgeB.vA = vB + 1;
			edgeB.vB = vA + 1;
			edgeB.weight = weight;
			gLists[ vB ].push_back( edgeB );
			
			return true;
		}
	}


	return false;
}

bool CGraph::AddDirectNegEdge( int vSrc, int vDst, int weight ) {

	struct edge edge;


	vSrc--;
	vDst--;

	if ( vSrc < cV && vDst < cV ) {

		if( type == Matrix ) {

			gMatrix[ vSrc ][ vDst ] = weight;

			return true;

		} else {

			edge.vA = vSrc + 1;
			edge.vB = vDst + 1;
			edge.weight = weight;
			gLists[ vSrc ].push_back( edge );

			return true;
		}
	}


	return false;
}

bool CGraph::IsConnected() {

	bool * connected = new bool[ cV ];
	vector< int > conseqs;


	connected[ 0 ] = true;

	conseqs = GetConsequents( 0 );

	DFS( connected, conseqs );

	for ( int i=0; i<cV; ++i ) {

		if( !connected[ i ] ) {

			return false;
		}
	}


	return true;
}

void CGraph::FillEdgesTree() {

	if( type==Matrix ) {

		for( int i=0; i<cV; i++ ) {
			
			for( int j=i+1; j<cV; j++ ) {

				if( gMatrix[i][j] > 0) {

					edge tmp;
					tmp.vA = i + 1;
					tmp.vB = j + 1;
					tmp.weight = gMatrix[i][j];
					edges.insert( tmp );
				}
			}
		}

	} else {

		/*vector< struct edge >::iterator itr;
		vector< vector< struct edge > >::iterator itr2;*/
		edge tmp;

		for (int i=0; i<gLists.size(); ++i) {

			for (int j=0; j<gLists[i].size(); ++j) {

				tmp.vA = gLists[i][j].vA;
				tmp.vB = gLists[i][j].vB;
				tmp.weight = gLists[i][j].weight;
				edges.insert( tmp );
			}
		}
		/*for( itr2=gLists.begin(); itr2!=gLists.end(); itr2++ ) {

			for( itr=(*itr2).begin(); itr!=(*itr2).end(); itr++ ) {

				tmp.vA = (*itr).vA;
				tmp.vB = (*itr).vB;
				tmp.weight = (*itr).weight;
				printf("%d\t%d %d %d\n", *itr2, (*itr).vA, (*itr).vB, (*itr).weight );
				edges.insert( tmp );
			}
		}*/
	}
}

void CGraph::DFS( bool * connected, vector< int > neighbours ) {

	int n_i;


	for (int i=0; i<neighbours.size(); ++i) {

		n_i = neighbours[i];
		if ( !connected[ n_i ] ) {

			connected[ n_i ] = true;

			DFS( connected, neighbours );
		}
	}
}